//
// Created by 啊汤哥 on 2025/6/29.
//
#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int value;
    struct TreeNode *left, *right;
    int ltag, rtag; // 左、右线索标志
} TreeNode;

TreeNode *pre = nullptr;

void visit(TreeNode * q) {
    if (q->left == nullptr) {
        q->left = pre;
        q->ltag = 1;
    }
    if (pre != nullptr && pre->right == nullptr) {
        pre->right = q;
        pre->rtag = 1;
    }
    pre = q;
}

// 中序
void InThread(TreeNode *tree_node) {
    if (tree_node != nullptr) {
        InThread(tree_node->left); // 中序遍历左子树
        visit(tree_node);  //  访问根节点
        InThread(tree_node->right);  // 中序遍历右子树
    }

}

// 先序
void PreThread(TreeNode *t) {
    if (t != nullptr) {
        visit(t);
        if (t->ltag == 0) {  // left不是前驱线索
            PreThread(t->left);
        }
        PreThread(t->right);
    }
}

// 中序遍历的线索二叉树
void CreateThread(TreeNode *t) {
    pre = nullptr;
    if (t != nullptr) {
        InThread(t);
        if (pre->right == nullptr) {
            pre->rtag = 1;
        }
    }
}

// 中序遍历线索二叉树 找后继节点 --> 左
TreeNode *FirstNode(TreeNode *p) {
    // 循环找到最左下角的节点
    while (p->ltag == 0) p = p->left;
    return p;
}
// 接着找到节点p的后继节点
TreeNode *NextNode(TreeNode *p) {
    // 右子树是最左下节点
    if (p->rtag == 0) {
        return FirstNode(p->right);
    }
    return p->right;
}

void InOrder(TreeNode *t) {
    for (TreeNode *p = FirstNode(t); p!=NULL; p=NextNode(p)) {
        visit(p);
    }
}



// 中序遍历线索二叉树 找前继节点 --> 右
TreeNode *LastNode(TreeNode *p) {
    // 循环找到最右下角的节点 如果当前节点不是线索（线索是1） 继续向下访问
    while (p->rtag == 0) p = p->right;
    return p;
}

// 接着找到节点p的后继节点
TreeNode *PreNode(TreeNode *p) {
    // 右子树是最左下节点
    if (p->ltag == 0) {
        return LastNode(p->left);
    }
    return p->left;
}

void RevInOrder(TreeNode *t) {
    for (TreeNode *p = LastNode(t); p!=NULL; p=PreNode(p)) {
        visit(p);
    }
}
